_A=None
class defaultdict:
    @staticmethod
    def __new__(cls,default_factory=_A,**kwargs):self=super(defaultdict,cls).__new__(cls);self.d={};return self
    def __init__(self,default_factory=_A,**kwargs):self.d=kwargs;self.default_factory=default_factory
    def __getitem__(self,key):
        try:return self.d[key]
        except KeyError:v=self.__missing__(key);self.d[key]=v;return v
    def __setitem__(self,key,v):self.d[key]=v
    def __delitem__(self,key):del self.d[key]
    def __contains__(self,key):return key in self.d
    def __missing__(self,key):
        if self.default_factory is _A:raise KeyError(key)
        return self.default_factory()